#pragma once
#include <iostream>
#include <assert.h>

using namespace std;

namespace zch{
    template<class T>
    struct list_node{
        list_node(const T& val)
        :_val(val)
        ,_prev(nullptr)
        ,_next(nullptr)
        {}
      
        T _val;
        list_node<T>* _prev;
        list_node<T>* _next;
    };

    template<class T, class Ref, class Ptr>
    struct _list_iterator{
        typedef list_node<T> node;
        typedef _list_iterator<T, Ref, Ptr> Self;
        node* _pnode;

        _list_iterator(node* pnode)
        :_pnode(pnode)
        {}

        Ref operator*()
        {
            return _pnode->_val ;
        }

        Ptr operator->()
        {
            return &_pnode->_val;
        }

        Self& operator++()
        {
            _pnode = _pnode->_next;
            return *this;
        }

        Self& operator--()
        {
            _pnode = _pnode->_prev;
            return *this;
        }

        Self operator++(int)
        {
            Self tmp(*this);
            _pnode = _pnode->_next;
            return tmp;
        }

        Self operator--(int)
        {
            Self tmp(*this);
            _pnode = _pnode->_prev;
            return tmp;
        }

        bool operator!=(const Self& it)
        {
            return _pnode != it._pnode;
        }

        bool operator==(const Self& it)
        {
            return _pnode == it._pnode;
        }
    };
    template<class T>
    class list{
        typedef list_node<T> node;
    public:
        typedef _list_iterator<T, T&, T*> iterator;
        typedef _list_iterator<T, const T&, const T*> const_iterator;
    public:
        iterator begin()
        {
            return iterator(_head->_next);
        }

        iterator end()
        {
            return iterator(_head);
        }

        const_iterator begin() const
        {
            return const_iterator(_head->_next);
        }

        const_iterator end() const
        {
            return const_iterator(_head);
        }

        void empty_initialize()
        {
            _head = new node(T());
            _head->_prev = _head;
            _head->_next = _head;

            _size = 0;
        }

        template<class InputIterator>
        list(InputIterator first, InputIterator last)
        {   
            empty_initialize();
            while(first != last)
            {
                push_back(*first);
                ++first;
            }
        }

        void swap(list<T>& lt)
        {
            std::swap(_head, lt._head);
            std::swap(_size, lt._size);
        }

        list()
        {
            empty_initialize();
        }

        list(const list<T>& lt)
        {
            empty_initialize();

            list<T> tmp(lt.begin(), lt.end());
            swap(tmp);
        }

        list<T>& operator=(list<T> lt)
        {
            swap(lt);
            return *this;
        }

        void print()
        {
            node* cur = _head->_next;
            while(cur != _head)
            {
                cout << cur->_val << " ";
                cur = cur->_next;
            }
            cout << endl;
        }

        iterator insert(iterator pos, const T& val)
        {
            node* newnode = new node(val);
            node* cur = pos._pnode;
            node* prev = cur->_prev;
            
            //插入
            prev->_next = newnode;
            newnode->_next = cur;
            newnode->_prev = prev;
            cur->_prev = newnode;

            ++_size;
            return iterator(newnode);
        }

        iterator erase(iterator pos)
        {
            assert(pos != end());

            node* next = pos._pnode->_next;
            node* prev = pos._pnode->_prev;

            prev->_next = next;
            next->_prev = prev;

            delete pos._pnode;
            --_size;

            return iterator(next);
        }

        void push_back(const T& val)
        {
            insert(end(), val);
        }

        void push_front(const T& val)
        {
            node* newnode = new node(T(val));
            node* next = _head->_next;
            
            //插入
            _head->_next = newnode;
            newnode->_next = next;
            next->_prev = newnode;
            newnode->_prev = _head;
            ++_size;
            // insert(begin(), val);
        }

        void pop_back()
        {
            assert(_size > 0);
            node* tmp = _head->_prev;
            node* prev = tmp->_prev;
            prev->_next = _head;
            _head->_prev = prev;
            --_size;

            delete tmp;
        }

        bool empty() const
        {
            return _size == 0;
        }

        size_t size()
        {
            return _size;
        }

        void clear()
        {
            iterator it = begin();
            while(it != end())
            {
                it = erase(it);
            }
        }

        ~list()
        {
            clear();

            delete _head;
            _head = nullptr;
            _size = 0;
        }
    private:
        node* _head;
        size_t _size;
    };


    void test1()
    {
        zch::list<int> lt;
        for(int i = 0; i < 10; ++i)
        {
            lt.push_back(i);
        }

        lt.print();
    }

    void test2()
    {
        zch::list<int> lt;
        for(int i = 0; i < 10; ++i)
        {
            lt.push_back(i);
        }
        lt.print();

        lt.push_back(10);
        lt.push_front(20);
        zch::list<int>::iterator i = lt.begin();
        while(i != lt.end())
        {
            cout << *i << " ";
            ++i;
        }
        cout << endl;

        lt.pop_back();
        lt.print();
        cout << lt.size() << endl;
        if(!lt.empty())
        {
            cout << "non-empty" << endl;
        }
    }

    void test3()
    {
        zch::list<int> lt1;
        for(int i = 0; i < 10; ++i)
        {
            lt1.push_back(i);
        }
        lt1.print();
        cout << lt1.size() << endl;
        zch::list<int> lt2(lt1);
        lt2.print();
        cout << lt2.size() << endl;

        zch::list<int> lt3;
        lt3 = lt2;
        lt3.print();
        cout << lt3.size() << endl;


        zch::list<int> lt4(lt3.begin(), lt3.end());
        lt4.erase(lt4.begin());
        lt4.erase(--lt4.end());
        lt4.print();
        cout << lt4.size() << endl;

        
    }
}
